Missing Number

LeetCode 268 | Difficulty: Easy

Easy

Problem Description

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]

Output: 2

Explanation:

n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]

Output: 2

Explanation:

n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]

Output: 8

Explanation:

n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

- `n == nums.length`

- `1 <= n <= 10^4`

- `0 <= nums[i] <= n`

- All the numbers of `nums` are **unique**.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Topics: Array, Hash Table, Math, Binary Search, Bit Manipulation, Sorting

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 120 ms)

Metric	Value
Runtime	120 ms
Memory	N/A
Date	2018-08-19

Solution

public class Solution {
    public int MissingNumber(int[] nums) {
        int res = nums.Length;
    for (int i = 0; i < nums.Length; i++)
    {
        res = res ^ i ^ nums[i];
    }
    return res; 
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Precisely define what the left and right boundaries represent, and the loop invariant.